#include <iostream>
#include <vector>
#include <ctime>
#include <functional>
#include <stack>
#include <queue>
using namespace std;

namespace YX
{
    template<typename T>
    class Sort
    {
        private:
            vector<T> _v;

            // hoare法
            template<class Func>
            void _Quick1(int begin,int end,Func func)
            {
                if(begin>=end)
                {
                    return;
                }

                int keyi=begin;
                int left=begin;
                int right=end;

                while(left<right)
                {
                    while( left<right && (func(_v[right],_v[keyi]) || _v[keyi]==_v[right]) )
                    {
                       right--; 
                    }

                    while( left<right && (func(_v[keyi],_v[left]) || _v[keyi]==_v[left]) )
                    {
                        left++;
                    }
    
                    std::swap(_v[left],_v[right]);

                }

                int midi=left;
                std::swap(_v[keyi],_v[midi]);

                _Quick1(begin,midi-1,func);
                _Quick1(midi+1,end,func);

            }

            // 填坑法
            template<class Func>
            void _Quick2(int begin,int end,Func func)
            {
                if(begin>=end)
                {
                    return;
                }

                T key=_v[begin];
                int hole=begin;
                int left=begin;
                int right=end;

                while(left<right)
                {
                    while(left<right && (func(_v[right],key) || _v[right]==key))
                    {
                        right--;
                    }

                    _v[hole]=_v[right];
                    hole=right;

                    while(left<right && (func(key,_v[left]) || _v[left]==key))
                    {
                        left++;
                    }
                    _v[hole]=_v[left];
                    hole=left;
                }

                int midi=left;
                _v[midi]=key;

                _Quick2(begin,midi-1,func);
                _Quick2(midi+1,end,func);
            }

            // 前后指针法
            template<class Func>
            void _Quick3(int begin,int end,Func func)
            {
                if(begin>=end)
                {
                    return;
                }

                T keyi=begin;
                int prev=begin;
                int curr=begin+1;

                while(curr<=end)
                {
                    if(func(_v[keyi],_v[curr]) && ++prev!=curr)
                    {
                        std::swap(_v[curr],_v[prev]);
                    }
                    curr++;
                }
    
                int midi=prev;

                std::swap(_v[keyi],_v[midi]);
                _Quick3(begin,midi-1,func);
                _Quick3(midi+1,end,func);
            }

        public:
            Sort(size_t n)
                :_v(n)
            {
                for(size_t i=0;i<n;i++)
                {
                    _v[i]=rand()%100;
                }
                Print();
            }

            void Print()
            {
                typename vector<T>::iterator it=_v.begin();
                while(it!=_v.end())
                {
                    cout<<*it<<" ";
                    it++;
                }
                cout<<endl;
            }

            template<class Func>
            void Quick(Func func)
            {
                //_Quick1(0,_v.size()-1,func);
                //_Quick2(0,_v.size()-1,func);
                _Quick3(0,_v.size()-1,func);
                Print();
            }


    };


};

namespace YX 
{
    template<typename T,typename Func=greater<T>>
    int QuickPrevNext(T* a,int begin,int end,Func func)
    {
        int keyi=begin;
        int prev=begin;
        int curr=begin+1;

        while(curr<=end)
        {
            if(func(a[keyi],a[curr]) && ++prev!=curr)
            {
                std::swap(a[keyi],a[curr]);
            }
            curr++;
        }
        std::swap(a[keyi],a[prev]);
        return prev;
    }

};

int main(int argc,char* argv[],char* env[])
{

    int arr[]={0,9,8,7,6,5,4,3,2,1};

    // 栈实现快排非递归


    int begin=0;
    int end=9;

    stack<int> st;
    st.push(end);
    st.push(begin);

    while(!st.empty())
    {
        int left=st.top();
        st.pop();
        int right=st.top();
        st.pop();

        int midi=YX::QuickPrevNext(arr,left,right,std::greater<int>());

        if(left<midi-1)
        {
            st.push(midi-1);
            st.push(left);
        }

        if(midi+1<right)
        {
            st.push(right);
            st.push(midi+1);
        }

    }


    for(int i=0;i<10;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;


   // srand((unsigned)time(nullptr));

   // YX::Sort<int> s(10);

   // s.Quick(less<int>());

   // return 0;
}
